package com.zsj.Tree;

import java.util.Stack;

/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/15 12:16
 * @Description
 */
public class LeetCodeTest {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 450. 删除二叉搜索树中的节点
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        //寻找待删除节点
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        //到这里说明找到了待删除节点
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        TreeNode s = root.right;
        while (s.left != null) s = s.left;
        s.right = deleteNode(root.right, s.val);
        s.left = root.left;
        return s;
    }


    //新增节点 题目保证了插入节点一定不存在树中
    public TreeNode insertBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        else if (root.val < val) root.right = insertBST(root.right, val);
        else if (root.val > val) root.left = insertBST(root.left, val);
        return root;
    }

    //700. 二叉搜索树中的搜索
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        while (root != null) {
            if (val < root.val) root = root.left;
            else if (val > root.val) root = root.right;
            else return root;
        }
        return null;
    }

    public TreeNode searchBST2(TreeNode root, int val) {
        if (root == null) return null;
        if (val < root.val) return searchBST2(root.left, val);
        else if (val > root.val) return searchBST2(root.right, val);
        else return root;
    }

    //验证二叉搜索树
    public boolean isValidBST(TreeNode root) {
        //中序遍历  二叉搜索树中序遍历的结果一定是有序的
        //所以我们只要发现了 在中序遍历的过程中 有第一个数字大于了第二个数字
        //返回false
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        long prev = Long.MIN_VALUE;//默认还不是0
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                if (prev > pop.val) return false;
                prev = pop.val;
                cur = pop.right;
            }
        }
        return true;
    }


    long prev = Long.MIN_VALUE;

    //递归 分而治之
    public boolean isValidBST2(TreeNode root) {
        if (root == null) return true;
        boolean af = isValidBST2(root.left);
        if (prev >= root.val) return false;
        prev = root.val;
        boolean bf = isValidBST2(root.right);
        return af && bf;
    }
}
